Namespacing everything to /UVa.
[andmenj-acm.git] / UVa / 843 - Crypt kicker / 843.cpp
blobc15c300879e9b2af4a13eddb5e00b4a7c77c0205
1 #include <sstream>
2 #include <iostream>
3 #include <map>
4 #include <string>
5 #include <vector>
6 #include <set>
8 using namespace std;
10 map<int, set<string> > dict;
11 map<char, char> solucion;
14 bool contradice(const string &origen, const string &destino, map<char, char> crypt){
15 //cout << "Contradice llamado con " << origen << " y " << destino << endl;
17 map<char, char> temp;
18 for (int i=0; i<origen.size(); ++i){
19 if (temp.count(origen[i]) == 1){
20 if (temp[origen[i]] != destino[i]){
21 return true;
23 }else{
24 for (map<char, char>::iterator j = temp.begin(); j != temp.end(); ++j){
25 if ((*j).second == destino[i]) return true;
27 temp[origen[i]] = destino[i];
31 if (origen.length() != destino.length()) return true;
33 for (int i=0; i<origen.size(); ++i){
34 if (crypt.count(origen[i]) == 1){
35 if (crypt[origen[i]] != destino[i]){
36 return true;
38 }else{
39 for (map<char, char>::iterator j = crypt.begin(); j != crypt.end(); ++j){
40 if ((*j).second == destino[i]) return true;
44 return false;
49 void asignar(const string &origen, const string &destino, map<char, char> &crypt){
50 if (origen.size() != destino.size()) return;
52 for (int i=0; i<origen.size(); ++i){
53 crypt[origen[i]] = destino[i];
57 bool bt(int i, const vector<string> &words, map<char, char> crypt){
58 if (i >= words.size()){
59 solucion = crypt;
60 return true;
63 int len = words[i].length();
64 set<string> possible = dict[len];
66 for (set<string>::iterator j = possible.begin(); j != possible.end(); ++j){
68 if (!contradice(words[i], (*j), crypt)){
69 map<char, char> copia = crypt;
70 asignar(words[i], (*j), copia);
72 if (bt(i+1, words, copia)){
73 return true;
78 return false;
81 int main(){
82 int n;
83 cin >> n;
84 while (n--){
85 string s;
86 cin >> s;
87 dict[s.length()].insert(s);
88 //cout << "agregue " << s << " al dict en la posicion " << s.length() << endl;
90 getchar();
91 string line;
92 while (getline(cin, line)){
93 //cout << "Lei esta linea: " << line << endl;
95 if (line == ""){
96 cout << "\n";
97 continue;
100 vector<string> words;
101 stringstream ss;
102 ss << line;
103 string word;
104 while (ss >> word){
105 words.push_back(word);
107 //cout << "Empuje la palabra " << word << " a la lista " << endl;
110 if (bt(0, words, map<char, char>() )){
111 for (int i=0; i<line.size(); ++i){
112 if (line[i] == ' ') cout << " ";
113 else cout << solucion[line[i]];
115 cout << endl;
116 //cout << "Hay solucion\n";
117 }else{
118 for (int i=0; i<line.size(); ++i){
119 if (line[i] == ' ') cout << " ";
120 else cout << "*";
122 cout << endl;
123 //cout << "No hay solucion\n";